<html>
<head>
	<meta charset="UTF-8">
	<meta content="IE=edge" http-equiv="X-UA-Compatible">
	<meta content="initial-scale=1.0, maximum-scale=1.0, user-scalable=no, width=device-width" name="viewport">
	<title>3342：[Ceoi2013]board</title>
	<!-- css -->
	<link href="../css/base.min.css" rel="stylesheet">
	<link href="../css/project.min.css" rel="stylesheet">
	
	<!-- favicon -->
	<!-- ... -->
</head>
<body class="page-brand">
	<header class="header header-transparent header-waterfall ui-header">
		<ul class="nav nav-list pull-left">
			<li>
				<a data-toggle="menu" href="#menu">
					<span class="icon icon-lg">menu</span>
				</a>
			</li>
		</ul>
		<a class="header-logo header-affix-hide margin-left-no margin-right-no" data-offset-top="213" data-spy="affix">[Ceoi2013]board</a>
		<span class="header-logo header-affix margin-left-no margin-right-no" data-offset-top="213" data-spy="affix">[Ceoi2013]board</span>
	</header>
	<nav aria-hidden="true" class="menu" id="menu" tabindex="-1">
		<div class="menu-scroll">
			<div class="menu-content">
				<a class="menu-logo" href="../index.html">BZOJ离线题库</a>
				<ul class="nav">
					<li>
						<a class="waves-attach" data-toggle="collapse" href="#problems">题目</a>
						<ul class="menu-collapse collapse in" id="problems">
							<li>
								<a class="waves-attach" href="../index.html">主页</a>
							</li>
							<li>
								<a class="waves-attach" href="../list.html">题目列表</a>
							</li>
						</ul>
					</li>
					<li>
						<a class="collapsed waves-attach" data-toggle="collapse" href="#about">关于</a>
						<ul class="menu-collapse collapse" id="about">
							<li>
								<a class="waves-attach" href="../about.html">关于此项目</a>
							</li>
						</ul>
					</li>
					
				</ul>
			</div>
		</div>
	</nav>
	<main class="content">
		<div class="content-header ui-content-header">
			<div class="container">
				<h1 class="content-heading">
                [Ceoi2013]board                </h1>
                <p>时间限制：1s&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;  空间限制：256MB</p>			</div>
		</div>
		<div class="container">
			<section class="content-inner margin-top-no">
				<div class="row">
					<div class="col-lg-13 col-md-13">
						<div class="card margin-bottom-no">
							<div class="card-main">
								<div class="card-inner">
									
                                <h3>题目描述</h3><p><div style="margin: 7.5pt 16.45pt 0pt 0cm; line-height: 13pt"><span style="font-size: medium"><span style="color: black">Mirko and Slavko have a new board game. The game board resembles a complete infinite binary tree. More precisely, the board consists of nodes and two-way roads connecting them. The root node is located at the </span></span></div>
<div style="margin: 0cm -1.5pt 0pt 0cm; line-height: 13.5pt; text-align: left" align="left"><span style="font-size: medium"><span style="color: black">top of the board and we say it is at <i>&nbsp;&nbsp; level zero</i>. Each node has exactly two children, the <i>&nbsp;&nbsp;&nbsp; left child</i> and the </span></span></div>
<div style="margin: 0cm -1.5pt 0pt 0cm; line-height: 13.5pt; text-align: left" align="left"><span style="font-size: medium"><i><span style="color: black">right child</span></i><span style="color: black">&nbsp;, located in the lower-left and the lower-right directions of the parent node. The level of a </span></span></div>
<div style="margin: 0cm 16.25pt 0pt 0cm; line-height: 12.65pt"><span style="font-size: medium"><span style="color: black">child node is one greater than the level of the parent node. In addition to roads connecting a parent node with its children, there are roads connecting all of the nodes at a particular level &ndash; for each level, starting from the leftmost node, there is a road connecting each node to the next node to the right on the same level. </span></span></div>
<div style="margin: 0cm -1.1pt 0pt 0cm; line-height: 10pt" align="left"><span style="font-size: medium"><span style="color: black">&nbsp;</span></span></div>
<div style="margin: 0cm -1.1pt 0pt 0cm; line-height: 10pt" align="left"><span style="font-size: medium"><span style="color: black">&nbsp;</span></span></div>
<div style="margin: 0cm -1.1pt 0pt 0cm; line-height: 10pt" align="left"><span style="font-size: medium"><span style="color: black">&nbsp;</span></span></div>
<div style="margin: 0cm -1.1pt 0pt 0cm; line-height: 10pt" align="left"><span style="font-size: medium"><span style="color: black">&nbsp;</span></span></div>
<div style="margin: 0cm -1.1pt 0pt 0cm; line-height: 10pt" align="left"><span style="font-size: medium"><span style="color: black">&nbsp;</span></span></div>
<div style="margin: 0cm -1.1pt 0pt 0cm; line-height: 10pt" align="left"><span style="font-size: medium"><span style="color: black">&nbsp;<img height="340" width="568" alt="" src="../file/3342_0.jpg" /></span></span></div>
<div style="margin: 0cm -1.1pt 0pt 0cm; line-height: 10pt" align="left"><span style="font-size: medium"><span style="color: black">&nbsp;</span></span></div>
<div style="margin: 0cm -1.1pt 0pt 0cm; line-height: 10pt" align="left"><span style="font-size: medium"><span style="color: black">&nbsp;</span></span></div>
<div style="margin: 0cm -1.1pt 0pt 0cm; line-height: 10pt" align="left"><span style="font-size: medium"><span style="color: black">&nbsp;</span></span></div>
<div style="margin: 0cm -1.1pt 0pt 0cm; line-height: 10pt" align="left"><span style="font-size: medium"><span style="color: black">&nbsp;</span></span></div>
<div style="margin: 0cm -1.1pt 0pt 0cm; line-height: 10pt" align="left"><span style="font-size: medium"><span style="color: black">&nbsp;</span></span></div>
<div style="margin: 0cm -1.1pt 0pt 0cm; line-height: 10pt" align="left"><span style="font-size: medium"><span style="color: black">&nbsp;</span></span></div>
<div style="margin: 0cm -1.1pt 0pt 0cm; line-height: 10pt" align="left"><span style="font-size: medium"><span style="color: black">&nbsp;</span></span></div>
<div style="margin: 0cm -1.1pt 0pt 0cm; line-height: 10pt" align="left"><span style="font-size: medium"><span style="color: black">&nbsp;</span></span></div>
<div style="margin: 0cm -1.1pt 0pt 0cm; line-height: 10pt" align="left"><span style="font-size: medium"><span style="color: black">&nbsp;</span></span></div>
<div style="margin: 0cm -1.1pt 0pt 0cm; line-height: 10pt" align="left"><span style="font-size: medium"><span style="color: black">&nbsp;</span></span></div>
<div style="margin: 0cm -1.1pt 0pt 0cm; line-height: 10pt" align="left"><span style="font-size: medium"><span style="color: black">&nbsp;</span></span></div>
<div style="margin: 0cm -1.1pt 0pt 0cm; line-height: 4pt" align="left"><span style="font-size: medium"><span style="color: black">&nbsp;</span></span><span style="font-size: medium"><b><span style="color: black">Figure 1: The second test example below </span></b></span></div>
<div style="margin: 0cm -1.1pt 0pt 0cm; line-height: 10pt" align="left"><span style="font-size: medium"><span style="color: black">&nbsp;</span></span></div>
<div style="margin: 0cm -1.5pt 0pt 0cm; line-height: 13.5pt" align="left"><span style="font-size: medium"><span style="color: black">Each <i>path</i> through the game board is a sequence of steps, each moving from a node to a different node via </span></span></div>
<div style="margin: 0cm -1.5pt 0pt 0cm; line-height: 13.5pt" align="left"><span style="font-size: medium"><span style="color: black">a single road. Each step can be described by a single character as follows: </span></span></div>
<div style="margin: 0.5pt -1.1pt 0pt 18pt; line-height: 13.5pt" align="left"><span style="font-size: medium"><span style="color: black">&middot; </span><span style="color: black">&nbsp;</span><span style="color: black">character &bdquo;1</span><span style="color: black">‟</span><span style="color: black"> describes moving from a node to its left child, </span></span></div>
<div style="margin: 0.5pt -1.1pt 0pt 18pt; line-height: 13.5pt" align="left"><span style="font-size: medium"><span style="color: black">&middot; </span><span style="color: black">&nbsp;</span><span style="color: black">character &bdquo;2</span><span style="color: black">‟</span><span style="color: black"> describes moving from a node to its right child, </span></span></div>
<div style="margin: 1.5pt -1.1pt 0pt 18pt; line-height: 13.5pt" align="left"><span style="font-size: medium"><span style="color: black">&middot; </span><span style="color: black">&nbsp;</span><span style="color: black">character &bdquo;U</span><span style="color: black">‟</span><span style="color: black"> describes moving from a node to its parent, </span></span></div>
<div style="margin: 0.5pt -1.1pt 0pt 18pt; line-height: 13.5pt" align="left"><span style="font-size: medium"><span style="color: black">&middot; </span><span style="color: black">&nbsp;</span><span style="color: black">character &bdquo;L</span><span style="color: black">‟</span><span style="color: black"> describes moving from a node to the next node to the left on the same level, </span></span></div>
<div style="margin: 1.5pt -1.1pt 0pt 18pt; line-height: 13.5pt" align="left"><span style="font-size: medium"><span style="color: black">&middot; </span><span style="color: black">&nbsp;</span><span style="color: black">character &bdquo;R</span><span style="color: black">‟</span><span style="color: black"> describes moving from a node to the next node to the right on the same level. </span></span></div>
<div style="margin: 0cm 16.8pt 0pt 0cm; line-height: 13pt"><span style="font-size: medium"><span style="color: black">For example, if we were to start at the root node and take the sequence of steps &bdquo;221LU</span><span style="color: black">‟</span><span style="color: black"> we would end up in the node denoted with the letter &bdquo;A</span><span style="color: black">‟</span><span style="color: black"> in the figure above. </span></span></div>
<div style="margin: 0cm -1.1pt 0pt 0cm; line-height: 10pt" align="left"><span style="font-size: medium"><span style="color: black">&nbsp;</span></span></div>
<div style="margin: 0cm -1.1pt 0pt 0cm; line-height: 8pt" align="left"><span style="font-size: medium"><span style="color: black">&nbsp;</span></span></div>
<div style="margin: 0cm -1.9pt 0pt 222.75pt; line-height: 13.5pt" align="left"><span style="font-size: medium"><b><span style="color: black">TASK </span></b></span></div>
<div style="margin: 7.5pt 16.15pt 0pt 0cm; line-height: 13pt"><span style="font-size: medium"><span style="color: black">Write a program that will, given two nodes on the board, find the smallest number of steps needed to go from one node to the other. The two nodes are given by specifying paths from the root node to them. If the two paths lead to the same node, the answer is zero. </span></span></div></p><hr/><h3>输入格式</h3><p><p class="MsoNormal" style="margin: 7.5pt 16.35pt 0pt 0cm; line-height: 13pt; mso-line-height-rule: exactly; mso-layout-grid-align: none"><span style="font-size: medium"><span lang="EN-US" style="color: black; font-family: &quot;Trebuchet MS&quot;; mso-bidi-font-size: 12.0pt; mso-font-kerning: 0pt">The first line of input contains a sequence of at most 100 000 characters &ndash; the path from the root to the first node. </span></span><span lang="EN-US" style="font-size: 10pt; color: black; font-family: &quot;Trebuchet MS&quot;; mso-bidi-font-size: 12.0pt; mso-font-kerning: 0pt"><o:p></o:p></span></p>
<p class="MsoNormal" style="margin: 0.5pt 16.2pt 0pt 0cm; line-height: 12pt; mso-line-height-rule: exactly; mso-layout-grid-align: none"><span style="font-size: medium"><span lang="EN-US" style="color: black; font-family: &quot;Trebuchet MS&quot;; mso-bidi-font-size: 12.0pt; mso-font-kerning: 0pt">The second line of input contains a sequence of at most 100 000 characters &ndash; the path from the root to the second node. </span></span><span lang="EN-US" style="font-size: 10pt; color: black; font-family: &quot;Trebuchet MS&quot;; mso-bidi-font-size: 12.0pt; mso-font-kerning: 0pt"><o:p></o:p></span></p>
<p class="MsoNormal" align="left" style="margin: 0.5pt -1.5pt 0pt 0cm; line-height: 13.5pt; text-align: left; mso-line-height-rule: exactly; mso-layout-grid-align: none"><span style="font-size: medium"><span lang="EN-US" style="color: black; font-family: &quot;Trebuchet MS&quot;; mso-bidi-font-size: 12.0pt; mso-font-kerning: 0pt">The two paths will be valid (it will be possible to make every move in both sequences). </span></span><span lang="EN-US" style="font-size: 10pt; color: black; font-family: &quot;Trebuchet MS&quot;; mso-bidi-font-size: 12.0pt; mso-font-kerning: 0pt"><o:p></o:p></span></p>
<p></p></p><hr/><h3>输出格式</h3><p><p class="MsoNormal" style="margin: 7.5pt 25.85pt 0pt 0cm; line-height: 13pt; mso-line-height-rule: exactly; mso-layout-grid-align: none"><span style="font-size: medium"><span lang="EN-US" style="color: black; font-family: &quot;Trebuchet MS&quot;; mso-bidi-font-size: 12.0pt; mso-font-kerning: 0pt">The first and only line of output should contain a single integer - the smallest number of steps needed to go from one node to the other. </span></span><span lang="EN-US" style="font-size: 10pt; color: black; font-family: &quot;Trebuchet MS&quot;; mso-bidi-font-size: 12.0pt; mso-font-kerning: 0pt"><o:p></o:p></span></p></p><hr/><h3>样例输入</h3><pre>221LU 
12L2 
</pre><hr/><h3>样例输出</h3><pre>3</pre><hr/><h3>提示</h3><p>没有写明提示</p><hr/><h3>题目来源</h3><p>没有写明来源</p>
								</div>
							</div>
						</div>
					</div>
				</div>
				
				
			</section>
		</div>
	</main>

	<div class="fbtn-container">
		<div class="fbtn-inner">
			<a class="fbtn fbtn-lg fbtn-brand-accent waves-attach waves-circle waves-light waves-effect" data-toggle="dropdown" aria-expanded="true"><span class="fbtn-text fbtn-text-left">Menu</span><span class="fbtn-ori icon">apps</span><span class="fbtn-sub icon">close</span></a>
			<div class="fbtn-dropup">
				<a class="fbtn fbtn-brand waves-attach waves-circle waves-light waves-effect" href="../list.html" target="_self"><span class="fbtn-text fbtn-text-left">题目列表</span><span class="icon">menu</span></a>
				<a class="fbtn fbtn-green waves-attach waves-circle waves-effect" href="../index.html" target="_self"><span class="fbtn-text fbtn-text-left">返回主页</span><span class="icon">home</span></a>
				<a class="fbtn waves-attach waves-circle waves-effect" href="http://www.lydsy.com/JudgeOnline/submitpage.php?id=3342" target="_blank"><span class="fbtn-text fbtn-text-left">提交代码</span><span class="icon">send</span></a>
				<a class="fbtn fbtn-orange waves-attach waves-circle waves-effect" href="http://www.lydsy.com/JudgeOnline/wttl/wttl.php?pid=3342" target="_blank"><span class="fbtn-text fbtn-text-left">试题讨论</span><span class="icon">chat</span></a>
				
			</div>
		</div>
	</div>

	<!-- js -->
	<script src="../js/jquery.min.js"></script>
	<script src="../js/base.min.js"></script>
	<script src="../js/project.min.js"></script>
</body>
</html>